home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 3112 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  3.1 KB
  1. Path: cymbal.aix.calpoly.edu!not-for-mail
  2. From: dstubbs@cymbal.aix.calpoly.edu (Dan Stubbs)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Fastest way to computer log(base2) of x?
  5. Date: 25 Jan 1996 17:44:04 -0800
  6. Organization: California Polytechnic State University, San Luis Obispo
  7. Message-ID: <4e9bl4$3ccp@cymbal.aix.calpoly.edu>
  8. References: <4e61iu$p6e@villa.fc.net> <4e6p7t$1n72@cymbal.aix.calpoly.edu> <4e8r54$n8q@ns.RezoNet.NET>
  9. NNTP-Posting-User: dstubbs@cymbal.aix.calpoly.edu
  10.  
  11. In article <4e8r54$n8q@ns.RezoNet.NET>, Ray Dunn <ray@ultimate-tech.com> wrote:
  12. >In referenced article, Dan Stubbs says...
  13.  
  14. >>It seems like an interesting exercise to find the left bit using
  15. >>binary search since moving an appropriate mask around (for
  16. >>speed) is a bit "different."  The following is for 32 bit ints,
  17. >>as you can see it is simple to modify for any width int that is
  18. >>a power of 2.
  19. >>
  20. >>/*------------------------------------------------------------------*/
  21. >>int  left_most_bit (int k) {
  22. >>/*   
  23. >> *   returns the position of the left most bit in k assuming that
  24. >> *      k != 0 and 32 bit ints. The algorithm used is essentially a
  25. >> *      binary search.
  26. >> */
  27. >>   unsigned posn = 0, width = 16, mask = 0xffff0000;
  28. >>
  29. >>   while (width > 1) {
  30. >>      if (k & mask) {
  31. >>         width /= 2;
  32. >>         mask <<= (posn + width);
  33. >>         mask >>=  posn;
  34. >>      }
  35. >>      else {
  36. >>         mask >>= width;
  37. >>         posn +=  width;
  38. >>      }
  39. >>   } 
  40. >>   if (k & mask) return posn;
  41. >>   else return posn+1;
  42. >>}
  43. >
  44. >I'm sorry, but there are an unreasonable number of errors in this 
  45.               *not true* -->^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  46. >code.  It's difficult to even see what you're trying to do, let alone 
  47.      *It does a binary search* -->^^^^^^^^^^^^^^^^^^^^^^^^^^
  48. >correct things like mask should be of unsigned type, and a possible 
  49. >reliance on right shift inserting zeros.  Please compile and test 
  50. >before posting.
  51. >
  52.  
  53. Indeed, the code above was compiled and tested. As advertised, it
  54. implements binary search in the "unusual" case where searching half
  55. the remaining list is accomplished using the & operator and an
  56. appropriate mask. It correctly identified the left most bit for
  57. over two billion test integers.
  58.  
  59. The only "error" in the code above is that int should be changed to
  60. unsigned in the declaration--so that it will work correctly for *all*
  61. compilers. The code above has been so changed. I still think it is an
  62. interesting variation on implementing binary search. 
  63.  
  64. Binary search is probably relatively slow in this case because the over-
  65. head of binary search doesn't really pay off while searching only
  66. 32 bits. Even sequential search will probably be faster--and certainly
  67. much shorter. For example, here is a (compiled and tested) implementation
  68. of sequential search.
  69.  
  70. +----------------------------------------------------+
  71. int left_most_bit (int k) {
  72.    unsigned posn = 0, mask = 0x80000000;
  73.  
  74.    while (!(k & mask)) {
  75.       mask >>= 1;
  76.       posn++;
  77.    }
  78.    return posn;
  79. }
  80. +----------------------------------------------------+
  81.  
  82. For speed I think a static array of masks to localize the search to
  83. (say four bits) followed by a sequential search might be good.
  84.